package BackTrack;

import 其他.DataStructure.TreeNode;
import MyUtils.TreeUtils;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树 从 中间 截断的 都是 遍历所有点 （只向下 or 岛屿那种）
 * <p>
 * <p>
 * i
 * if
 * 体
 * sI
 */
public class 路径总和III437 {

    List<TreeNode> rootList = new ArrayList<>();
    public void getAllNode(TreeNode root) {
        if (root == null) {
            return;
        }
        rootList.add(root);
        getAllNode(root.left);
        getAllNode(root.right);
    }

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    public void backTrack(TreeNode cur, int sum) {
        /* 回溯 debug */
        // System.out.print(cur == null ? "N " : cur.val+" ");

        if (cur == null) {
            return;
        }

        int newSum = sum + cur.val;
        tmp.add(cur.val);
        if (newSum == tar) {
            res.add(new ArrayList<>(tmp));
        }

        backTrack(cur.left, newSum);
        backTrack(cur.right, newSum);

        tmp.remove(tmp.size() - 1);
    }

    int tar = 0;
    public int pathSum(TreeNode root, int targetSum) {
        tar = targetSum;
        getAllNode(root);
        // 遍历 所有点 -> 当起点
        for (TreeNode curRoot : rootList) {
            // 每个起点向下找
            backTrack(curRoot, 0);
        }
        return res.size();
    }

    @Test
    public void test() {
        TreeNode root = TreeUtils.strToTree("10,5,-3,3,2,null,11,3,-2,null,1");
        System.out.println("RES:" + pathSum(root, 8));
    }
}
